/**
*  @file MergeCircleDoubleLink.c
 *  @desc 实现两个双向循环链表的合并功能（尾部拼接），并支持基本插入、删除、打印等操作。
 *        使用带头结点的双向循环链表结构。
 *        核心函数 mergeCircleDoubleLink 将两个循环链表合并为一个完整循环结构。
 *  @author WangBlue (wangjiping596@gmail.com)
 *  @date 2025-08-04 11:15
 *  @version 1.0
 */


#include <stdio.h>
#include <stdlib.h>

// ====================== 双向链表结构定义 ======================

/**
 * @struct node
 * @brief 双向循环链表的节点结构
 *
 * - data：存储数据
 * - next：后继节点指针
 * - pre ：前驱节点指针
 */
typedef struct node {
    int data;
    struct node *next;
    struct node *pre;
} node, *link;

// ====================== 基础操作函数 ======================

/**
 * @brief 创建一个新节点
 * @param value 节点数据
 * @return 成功返回新节点指针，失败返回 NULL
 */
link createNode(int value) {
    link newNode = (link) malloc(sizeof(node));
    if (newNode == NULL) return NULL;
    newNode->data = value;
    newNode->next = NULL;
    newNode->pre = NULL;
    return newNode;
}

/**
 * @brief 初始化链表头节点（带头结点，构成循环）
 * @param head 链表头指针的地址
 */
void initNode(link *head) {
    link newNode = createNode(0);  // 头节点不存储有效数据
    if (newNode == NULL) return;
    *head = newNode;

    newNode->next = newNode;
    newNode->pre  = newNode;
}

/**
 * @brief 打印链表内容（跳过头节点）
 * @param head 链表头
 */
void printList(link head) {
    if (head == NULL || head->next == head) return;

    link cur = head->next;
    while (cur != head) {
        printf("value is %d\n", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

/**
 * @brief 头插法插入新节点
 * @param head 链表头
 * @param value 插入的数据值
 */
void istHead(link head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;

    newNode->next = head->next;
    newNode->pre = head;

    head->next->pre = newNode;
    head->next = newNode;
}

/**
 * @brief 尾插法插入新节点
 * @param head 链表头
 * @param value 插入的数据值
 */
void istTail(link head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;

    link last = head->pre;

    newNode->next = head;
    newNode->pre = last;

    last->next = newNode;
    head->pre = newNode;
}

/**
 * @brief 删除第 pos 个节点（从 1 开始）
 * @param head 链表头
 * @param pos 删除位置（从1开始）
 */
void delByPos(link head, int pos) {
    if (head == NULL || head->next == head || pos < 1) return;

    link cur = head->next;
    int idx = 1;
    while (cur != head && idx < pos) {
        cur = cur->next;
        idx++;
    }

    if (cur == head) return;  // 超出范围

    cur->pre->next = cur->next;
    cur->next->pre = cur->pre;

    free(cur);
}

/**
 * @brief 在第 pos 个节点前插入一个值（从1开始）
 * @param head 链表头
 * @param pos 插入位置
 * @param value 插入值
 */
void istByPos(link head, int pos, int value) {
    if (pos < 1) return;

    link cur = head;
    int idx = 0;

    while (cur->next != head && idx < pos - 1) {
        cur = cur->next;
        idx++;
    }

    if (idx != pos - 1) return;

    link newNode = createNode(value);
    if (newNode == NULL) return;

    newNode->next = cur->next;
    newNode->pre = cur;

    cur->next->pre = newNode;
    cur->next = newNode;
}

// ====================== 合并两个循环链表 ======================

/**
 * @brief 将两个双向循环链表合并（尾部拼接）
 *
 * - la 的尾部连接 lb 的头部（跳过 lb 的哨兵头节点）
 * - lb 的尾部再连接回 la 的头节点，形成一个新的完整循环链表
 *
 * 合并后 la 是合并链表的头，lb 的头节点仍存在但不再在主链中
 *
 * @param la 链表 A 的头节点
 * @param lb 链表 B 的头节点
 */
void mergeCircleDoubleLink(link la, link lb) {
    if (la == NULL || lb == NULL || lb->next == lb) return;

    // la 的尾节点
    link pa = la->pre;

    // lb 的首节点和尾节点
    link firstB = lb->next;
    link lastB = lb->pre;

    // 1. la 尾节点连向 lb 的首节点
    pa->next = firstB;
    firstB->pre = pa;

    // 2. lb 的尾节点连回 la 的头节点
    lastB->next = la;
    la->pre = lastB;

    // （可选）断开 lb 头节点的连接，避免误用
    lb->next = lb;
    lb->pre = lb;
}

// ====================== 主函数 ======================

int main() {
    // 初始化第一个链表 head1
    link head1 = NULL;
    initNode(&head1);
    istTail(head1, 1);
    istTail(head1, 2);
    istTail(head1, 3);

    // 初始化第二个链表 head2
    link head2 = NULL;
    initNode(&head2);
    istTail(head2, 4);
    istTail(head2, 5);
    istTail(head2, 6);

    // 合并 head2 到 head1
    mergeCircleDoubleLink(head1, head2);

    // 打印合并后的链表
    printList(head1);

    return 0;
}
